home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
HPAVC
/
HPAVC CD-ROM.iso
/
BG_SRC.ZIP
/
BG_MOVE.C
< prev
next >
Wrap
C/C++ Source or Header
|
1992-05-30
|
20KB
|
615 lines
/*
*
* B G _ M O V E . C , moving and placing the pieces
* O.F.Ransen: 21st June 1991
* This version: 30th May 1992
*
*/
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include "bg.h"
/***************************************************************************/
char Globerr[GERR_LEN] = "" ;
const Layout_t Initial_Layout = {0, /* the bar */
2,0,0,0,0,0, /* two runners */
0,0,0,0,0,5,
0,0,0,0,3,0,
5,0,0,0,0,0, /* home */
0} ;
void Initial_Board (Layout_t Layouts[2])
/*
PURPOSE: To initial the layouts to the start of a game.
*/
{
short p ;
for (p = 0 ; p < N_PLACES ; p++) {
Layouts [BLACK_PLAYER][p] = Initial_Layout [p] ;
Layouts [WHITE_PLAYER][p] = Initial_Layout [p] ;
}
}
/*************************************************************************/
void Select_Best_Move (Dice_t* The_Dice,
Layout_t My_Old, Layout_t His_Old,
Transit_t* My_Best_Tr, Transit_t* His_Best_Tr,
Player_t Player, Search_t Search)
/*
PURPOSE: Given the current situation and the two Dice I return
with the best move possible contained in the
new layouts.
NOTES: 1) The Transit_t returned show us the new Layouts and how
we got there.
2) If the search type is Max_Only then we are just searching
for the largest number of moves possible, and when we find it
we can stop searching.
*/
{
Transit_t My_Old_Tr,His_Old_Tr ;
(void)strcpy (Globerr,"Select_Best_Move 1") ;
Init_Transit (My_Best_Tr,My_Old) ;
Init_Transit (His_Best_Tr,His_Old) ;
Copy_Transit (&My_Old_Tr,My_Best_Tr) ;
Copy_Transit (&His_Old_Tr,His_Best_Tr) ;
if (The_Dice->N_Vals == 4) {
/* No problems with order of moves, all 4 the same */
Lay_Sel_t Best_Score ;
Best_Score.Goodness = WORST_SCORE ;
Best_Score.Moves_Made = WORST_SCORE ;
Select_Best_Ndice_Move (The_Dice,3,
&My_Old_Tr,&His_Old_Tr,
My_Best_Tr,His_Best_Tr,
&Best_Score,Player,Search) ;
} else if (The_Dice->N_Vals == 2) {
/* Problems with order */
Select_Best_2Dice_Move (The_Dice,
&My_Old_Tr,&His_Old_Tr,
My_Best_Tr,His_Best_Tr,Player) ;
} else {
Error_Exit ("The_Dice->N_Vals very strange...") ;
}
Check_Layout (My_Best_Tr->Layout, "Checking Mine_New") ;
Check_Layout (His_Best_Tr->Layout,"Checking His_New") ;
(void)strcpy (Globerr,"Select_Best_Move 2") ;
}
/*************************************************************************/
void Select_Best_2Dice_Move (Dice_t* The_Dice,
Transit_t* My_Old_Tr, Transit_t* His_Old_Tr,
Transit_t* My_Best_Tr, Transit_t* His_Best_Tr,
Player_t Player)
/*
PURPOSE: To select the best move trying first Dice_AB and then Dice_BA
sequence.
NOTES: 1) If we see we are at the opening move of the game then we
do one of the standard moves contained in BG_STDOP.C
*/
{
Transit_t My_AB,My_BA,His_AB,His_BA ;
Lay_Sel_t Best_Score_AB,Best_Score_BA ;
boolean Copy_AB,Copy_BA ;
char Temp ;
(void)strcpy (Globerr,"Select_Best_2Dice_Move 1") ;
if (Standard_Opening (The_Dice,
My_Old_Tr, His_Old_Tr,
My_Best_Tr, His_Best_Tr)) {
return ;
}
Copy_Transit (&My_AB,My_Old_Tr) ;
Copy_Transit (&My_BA,My_Old_Tr) ;
Copy_Transit (&His_AB,His_Old_Tr) ;
Copy_Transit (&His_BA,His_Old_Tr) ;
Best_Score_AB.Goodness = WORST_SCORE ;
Best_Score_AB.Moves_Made = WORST_SCORE ;
Select_Best_Ndice_Move (The_Dice,1,
My_Old_Tr,His_Old_Tr,
&My_AB,&His_AB,
&Best_Score_AB,Player,Bestest) ;
(void)strcpy (Globerr,"Select_Best_2Dice_Move 2") ;
/* Swap dice order... */
Temp = The_Dice->Values[0] ;
The_Dice->Values[0] = The_Dice->Values[1] ;
The_Dice->Values[1] = Temp ;
Best_Score_BA.Goodness = WORST_SCORE ;
Best_Score_BA.Moves_Made = WORST_SCORE ;
Select_Best_Ndice_Move (The_Dice,1,
My_Old_Tr,His_Old_Tr,
&My_BA,&His_BA,
&Best_Score_BA,Player,Bestest) ;
(void)strcpy (Globerr,"Select_Best_2Dice_Move 3") ;
if (Best_Score_AB.Moves_Made > Best_Score_BA.Moves_Made) {
Copy_AB = TRUE ;
Copy_BA = FALSE ;
} else if (Best_Score_BA.Moves_Made > Best_Score_AB.Moves_Made) {
Copy_BA = TRUE ;
Copy_AB = FALSE ;
} else if (Best_Score_BA.Moves_Made != 0) {
/* Moves_Made are equal and non zero in both cases, choose the best */
if (Best_Score_AB.Goodness > Best_Score_BA.Goodness) {
Copy_AB = TRUE ;
Copy_BA = FALSE ;
} else {
Copy_BA = TRUE ;
Copy_AB = FALSE ;
}
} else {
Copy_BA = FALSE ;
Copy_AB = FALSE ;
}
(void)strcpy (Globerr,"Select_Best_2Dice_Move 4") ;
if (Copy_AB) {
Copy_Transit (My_Best_Tr,&My_AB) ;
Copy_Transit (His_Best_Tr,&His_AB) ;
} else if (Copy_BA) {
Copy_Transit (My_Best_Tr,&My_BA) ;
Copy_Transit (His_Best_Tr,&His_BA) ;
}
(void)strcpy (Globerr,"Select_Best_2Dice_Move 5") ;
}
/*************************************************************************/
void Select_Best_Ndice_Move (Dice_t* Dice_List, short This_Dice,
Transit_t* My_Curr_Tr, Transit_t* His_Curr_Tr,
Transit_t* My_Best_Tr, Transit_t* His_Best_Tr,
Lay_Sel_t* Best_Score, Player_t Player,
Search_t Search)
/*
PURPOSE: To select the best or most legal move so far.
NOTES : 1) If Depth_Only then we don't care about the goodness of the
move, only the legality of it. And we stop searching as soon
as we have found a legal move of 4, the maximum possible.
2) If This_Dice = -1 then we have stopped recursion, obviously
*/
{
static short Moves_Done = 0 ;
if (Won (My_Best_Tr->Layout,His_Best_Tr->Layout) > NO_WIN) {
return ;
}
#if DEBUG_SOURCE
(void)strcpy (Globerr,"Select_Best_Ndice_Move 1") ;
Check_Layout (My_Curr_Tr->Layout,"Checking My_Curr_Tr") ;
Check_Layout (His_Curr_Tr->Layout,"Checking His_Curr_Tr") ;
if (This_Dice > 3) {
printf ("\nInvalid Dice value: %d",This_Dice) ;
Error_Exit ("Invalid Dice value") ;
}
#endif
if (This_Dice >= 0) {
char p ;
boolean Something_Moved ;
Something_Moved = FALSE ;
for (p = BAR_I ; p <= POINT24_I ; p++) {
if (Can_Move (p,Dice_List->Values[This_Dice],
My_Curr_Tr->Layout,His_Curr_Tr->Layout)) {
/* It is ok to move from 'p' with this dice value */
Transit_t My_Temp,His_Temp ;
Something_Moved = TRUE ;
Copy_Transit (&My_Temp,My_Curr_Tr) ;
Copy_Transit (&His_Temp,His_Curr_Tr) ;
Execute_Move (p,Dice_List->Values[This_Dice],
&My_Temp,&His_Temp) ;
Moves_Done++ ;
if (Moves_Done > 4) {
Error_Exit ("Moves_Done > 4") ;
}
(void)strcpy (Globerr,"Select_Best_Ndice_Move 2") ;
/* Recurse... */
Select_Best_Ndice_Move (Dice_List, This_Dice-1,
&My_Temp,&His_Temp,
My_Best_Tr,His_Best_Tr,
Best_Score,Player,Search) ;
Moves_Done-- ;
}
}
if (!Something_Moved) {
/* No more moves possible in this branch, end recursion
and choose a move. */
(void)strcpy (Globerr,"Select_Best_Ndice_Move 3") ;
Choose_Move (My_Curr_Tr, His_Curr_Tr,
Player,Moves_Done,
My_Best_Tr,His_Best_Tr,Best_Score,Search) ;
}
if (Moves_Done < 0) {
Error_Exit ("Moves < 0 ") ;
}
} else {
/* No more dice, see if this any better than previous best */
if ((Search == Legalest) && (Best_Score->Moves_Made == 4)) {
/* No more choosing to do, we already know the maximum number
of moves to do */
return ;
}
Choose_Move (My_Curr_Tr,His_Curr_Tr,
Player,Moves_Done,
My_Best_Tr,His_Best_Tr,Best_Score,Search) ;
}
}
/*************************************************************************/
void Choose_Move (Transit_t* Mine, Transit_t* His,
Player_t Player, short Moves_Done,
Transit_t* My_Best, Transit_t* His_Best,
Lay_Sel_t* Best_Score, Search_t Search)
/*
PURPOSE: We have to choose between two moves, the previous best and
the one handed to us here.
NOTES: 1) We change the best variables to this one if it is better.
2) The number of moves made takes precedence over the goodness
of the move. According to the rules of Backgammon you must
make the most moves possible.
3) Usually this is the function called at the end of a recursive
branch.
4) If the search type is just looking for max moves then we do
not evaluate the move, just look at the Moves_Done, to get
a legal move.
*/
{
boolean Copy ;
long Goodness ;
(void)strcpy (Globerr,"Choose_Move 1") ;
if (Search == Bestest) {
Goodness = Evaluate_Move (Mine->Layout,His->Layout,Player) ;
} else if (Search == Legalest) {
Goodness = 0 ;
} else {
Error_Exit ("Bad Search value in Choose_Move") ;
}
if (Moves_Done < Best_Score->Moves_Made) {
Copy = FALSE ; /* The best move so far has moved more pieces than
this current move, so do not change the best move. */
} else {
if (Goodness > (Best_Score->Goodness)) {
/* An obviously better move */
Copy = TRUE ;
} else if (Goodness == (Best_Score->Goodness)) {
/* Choose at random between the two equal valued moves */
Copy = (Int_Rand_Range (0,100) > 50) ;
} else {
/* Not at all a good move */
Copy = FALSE ;
}
}
if (Copy) {
Copy_Transit (My_Best,Mine) ;
Copy_Transit (His_Best,His) ;
Best_Score->Goodness = Goodness ;
Best_Score->Moves_Made = Moves_Done ;
}
}
/*************************************************************************/
void Execute_Move (char p, char Die, Transit_t* Mine, Transit_t* His)
/*
PURPOSE: To move a piece from point p Die spaces forward. We will
eat one of his pieces if there is one. We record the new layouts
and move made in the transit types.
*/
{
char New_Point,His_Point,Places_Moved ;
New_Point = p + Die ;
if (New_Point > HOME_I) {
Places_Moved = Die - (New_Point - HOME_I) ;
New_Point = HOME_I ;
} else {
Places_Moved = Die ;
}
His_Point = Reverse_Index(New_Point) ;
#if DEBUG_SOURCE
if (Mine->Layout[p] < 1) {
Error_Exit ("Trying to move a piece from an empty point") ;
} else if ((His->Layout[His_Point] > 1) && (New_Point != HOME_I)){
Error_Exit ("Trying to move a piece to a blocked point") ;
}
#endif
/* Move my piece in the layout */
Mine->Layout [p]-- ;
Mine->Layout [New_Point]++ ;
/* Record how the transit was made */
Mine->Old_Points [Mine->N_Moves] = p ;
Mine->Places_Movd[Mine->N_Moves] = Places_Moved ;
/* Remember that Row is number of pieces-1 */
Mine->Old_Row [Mine->N_Moves] = Mine->Layout[p] ;
Mine->New_Row [Mine->N_Moves] = Mine->Layout[New_Point]-1 ;
Mine->N_Moves++ ;
/* Eat his piece ? ... */
if ((His_Point != BAR_I) && (His_Point != HOME_I)) {
if (His->Layout[His_Point] == 1) {
/* Move the point eaten back to the bar */
His->Layout[His_Point] = 0 ;
His->Layout[BAR_I]++ ;
/* Record how his piece moved back to the bar */
His->Old_Points [His->N_Moves] = His_Point ;
His->Places_Movd[His->N_Moves] = BAR_I - His_Point ;
His->Old_Row [His->N_Moves] = 0 ;
His->New_Row [His->N_Moves] = His->Layout[BAR_I]-1 ;
His->N_Moves++ ;
} else {
His->N_Moves = 0 ;
}
} else {
His->N_Moves = 0 ;
}
}
/*************************************************************************/
boolean Can_Move (char p, char Die, Layout_t Me, Layout_t Him)
/*
PURPOSE: To return TRUE if a move is possible.
*/
{
short New_Point ;
if (Me[p] == 0) {
/* I have no pieces on this point */
return (FALSE) ;
}
New_Point = p+Die ;
if (New_Point > HOME_I) {
/* The new point would be home */
New_Point = HOME_I ;
}
if ((Him[Reverse_Index(New_Point)] > 1) && (New_Point != HOME_I)) {
/* He is occupying where I would have gone */
return (FALSE) ;
}
if (New_Point == HOME_I) {
/* I want to go home... */
if (!Bearing_Off(Me)) {
/* ...but I am not bearing off. */
return (FALSE) ;
} else if ((p+Die) == HOME_I) {
/* ...and can move exactly to home */
return (TRUE) ;
} else if (Pieces_Behind(Me,p)) {
/* ...but pieces behind me, so cannot take piece home. */
return (FALSE) ;
}
}
if ((p != BAR_I) && (Me[BAR_I] != 0)) {
/* Trying to move a non bar piece while still on bar */
return (FALSE) ;
}
return (TRUE) ;
}
/*************************************************************************/
void Copy_Layout (Layout_t Dst, Layout_t Src)
/*
PURPOSE: To copy the Src to the Dst.
*/
{
ushort p ;
for (p = 0 ; p < N_PLACES ; p++) {
Dst[p] = Src[p] ;
}
}
/*************************************************************************/
boolean Bearing_Off (Layout_t Lay)
/*
PURPOSE: To return TRUE if all the pieces on the layout are in the
final quadrant.
*/
{
ushort p ;
p = BAR_I ;
do {
if (Lay[p] != 0) {
return (FALSE) ;
}
p++ ;
} while (p < 19) ;
return (TRUE) ;
}
/*************************************************************************/
short Won (Layout_t Me, Layout_t Him)
/*
PURPOSE: To return 0,SIMPLE,GAMMON or BACKGAMMON according to the layout.
*/
{
short p ;
if (Me[HOME_I] == N_PIECES) {
/* We have won, now work out by how much */
if (Him[HOME_I] > 0) {
/* He has taken off at least one piece */
return (SIMPLE) ;
} else {
/* It all depends on where is the last piece */
for (p = BAR_I ; p < HOME_I ; p++ ) {
if (Him[p] > 0) {
break ;
}
}
if (p < 7) {
/* He has a piece in my inner table */
return (BACKGAMMON) ;
} else {
return (GAMMON) ;
}
}
} else {
return (NO_WIN) ;
}
}
/*************************************************************************/
boolean Pieces_Behind (Layout_t Me, short p)
/*
PURPOSE: To return TRUE if there are any of my pieces further behind than
p.
*/
{
p-- ;
while (p >= 0) {
if (Me[p]) {
return (TRUE) ;
}
p-- ;
}
return (FALSE) ;
}
/*************************************************************************/
void Check_Layout (Layout_t Layout, char* Err_Mess)
/*
PURPOSE: To check that the layout is legal, exiting with an
error message if it is not.
*/
{
short Total,p ;
Total = 0 ;
for (p = BAR_I ; p < N_PLACES ; p++) {
Total = Total + Layout[p] ;
}
if (Total != N_PIECES) {
printf ("\nERROR: Total = %d",(int)Total) ;
printf ("\n ") ;
for (p = 0 ; p < N_PLACES ; p++) {
printf ("%3d",p) ;
}
printf ("\nM") ;
for (p = 0 ; p < N_PLACES ; p++) {
printf ("%3d",Layout[p]) ;
}
Error_Exit (Err_Mess) ;
}
}
/*************************************************************************/
void Copy_Transit (Transit_t* Dest, Transit_t* Source)
/*
PURPOSE: To copy the source transit into the destination transit
*/
{
short m ;
#if DEBUG_SOURCE
if ((Source->N_Moves > 4) || (Source->N_Moves < 0)) {
printf ("\nCopy_Transit, N_Moves = %d",Source->N_Moves) ;
Error_Exit ("bad N_Moves in Copy_Transit") ;
}
#endif
Copy_Layout (Dest->Layout,Source->Layout) ;
Dest->N_Moves = Source->N_Moves ;
for (m = 0 ; m < Dest->N_Moves ; m++) {
#if DEBUG_SOURCE
if ((Source->Old_Points[m] + Source->Places_Movd[m]) > HOME_I) {
printf ("\nERROR Points[%d]=%d Source->Places_Movd[%d]",
m,Source->Old_Points[m] + Source->Places_Movd[m],m) ;
Error_Exit ("in Copy_Transit Old+Places_Moved > HOME_I") ;
}
#endif
Dest->Old_Points [m] = Source->Old_Points [m] ;
Dest->Places_Movd [m] = Source->Places_Movd [m] ;
Dest->Old_Row [m] = Source->Old_Row [m] ;
Dest->New_Row [m] = Source->New_Row [m] ;
}
}
/*************************************************************************/
void Init_Transit (Transit_t* New, Layout_t Old)
/*
PURPOSE: To copy the Old layout into the transit and init everything
else to zero.
*/
{
Copy_Layout (New->Layout,Old) ;
New->N_Moves = 0 ;
}
/*************************************************************************/
boolean Move_Possible (Layout_t P_Lay, Layout_t O_Lay)
/*
Returns TRUE if the the Players layout is not completly blocked by
the Opponents layout.
*/
{
if (P_Lay [BAR_I] == 0) {
return (TRUE) ;
} else {
/* The player has a piece on the bar, has the opponent blocked
all six entry points? */
short p ;
for (p = 19 ; p <= POINT24_I ; p++) {
if (O_Lay[p] < 2) {
return (TRUE) ; /* ...no, we can get out here */
}
}
return (FALSE) ; /* .. yes, all six blocked */
}
}
/*************************************************************************/